A password is a special sequence of characters that uniquely "authenticates", i.e., confirms a user's identity, to a computer system and that is used for security purposes to control access to information and operations of the computer. Specifically, each user of the system is associated with an "account" that includes access rights to the computer's resources. In addition, each account has a name and a password, the latter being known only to the user authorized to access the account. Passwords are typically assigned to accounts as they are created, although many systems allow the users to change their passwords to any sequence of characters they desire.
When allowed to select their own passwords, users tend to choose passwords that are easily remembered; unfortunately, these passwords may also be easily guessed. One common threat to a password-based authentication system is an impostor capable of guessing the password of an authorized user. With the use of an automated system configured to generate character sequences at a high rate, the impostor can quickly "guess" large numbers of common names and words, typically by replaying every word in a dictionary. This is called a "dictionary attack".
In a stand-alone computer, the operating system has the responsibility for authenticating users. That is, upon presentation of a valid user's password during a login procedure, the operating system verifies the identity of the user by checking the presented password against a list of valid passwords. This type of authentication procedure may prevent a dictionary attack because, after a certain number of wrong guesses, the operating system can disable the account being attacked. Such an attack is, however, difficult to prevent in a distributed data processing network if there is no centralized intermediary that can observe the guesses.
A distributed network system typically includes various computer nodes interconnected by a communications medium. In many distributed systems, the user must send a password to each remote node in order to access its resources. If the user has the same password on all systems, the local node can save the entered password and automatically send it to the remote nodes when needed. In any case, this type of "remote" authentication is susceptible to another common, password-based system threat known as eavesdropping, i.e., interception of the password by wiretapping the network. If successful, eavesdropping can permit impersonation of the user by means of the intercepted password. To counter such a threat, cryptography is often used to preserve the confidentiality of the transmitted password when authenticating the user to remote nodes.
A third threat to a password-based authentication system is the penetration of a node that stores each authorized user's password for the purpose of authenticating each user to the system. Here, successful penetration of the node will allow the intruder to learn the passwords of all users. This threat can also be addressed with cryptography, although it is not always possible to protect against each threat in a single system.
The computer nodes described herein may include nodes that are directly accessed by users, e.g., workstations, and nodes running specialized applications, e.g., servers. These nodes, the processes running on these nodes and the users of the distributed system are called "principals". The authentication exchange described herein is performed on behalf of the principals.
A well-known cryptographic technique used to perform remote authentication is public key cryptography. In this method of secure communication, each principal has a public encryption key and a private encryption key, and two principals can communicate knowing only each other's public keys. An encryption key is a code or number which, when taken together with an encryption algorithm, defines a unique transformation used to encrypt or decrypt data. A public key system may be used in such a way as to ensure confidentiality of the information being transmitted, i.e., to ensure that the information may not be understood by an eavesdropper, as well as to ensure the authenticity of the sender of the information. The specific public key technique described herein is an RSA encryption scheme. It will, however, be understood to those skilled in the art that other public key systems may be used.
According to this type of encryption, the private key is known only to the owner of the key, while the public key is known to other principals in the system. Public key cryptography is also called "asymmetric" encryption because information encoded with one of the key pair may be decoded only by using the other key in the pair. With RSA crytptography, a principal's public and private keys are selected such that the transformations that they effect are mutual inverses of each other and the sequential application of both transformations, in either order, will first encode the information and then decode it to restore the information to its original form.
Accordingly, to effect a secure transmission of information to a recipient, a principal encodes ("encrypts") the information with the recipient's public key. Since only the intended recipient has the complementary private key, only that principal can decode ("decrypt") it. On the other hand, to prove to a recipient of information that the sender is who he purports to be, the sender encodes ("signs") the information with its private key. If the recipient can decode ("verify") the information, it knows that the sender has correctly identified itself.
Operation of a public key cryptography system will now be described with reference to an illustrative login authentication exchange between a workstation, acting on behalf of a user, and a remote server. Such operation may be understood without reference to the specific transformations that are used for encryption and decryption. Basically, the workstation encrypts a message for confidentiality by performing a transformation using the server's public key, and the server decrypts the message by performing a transformation using its private key.
Specifically, a user logs into the workstation with the user's password and the workstation derives a secret, non-complementary, encryption key by applying a known hash algorithm to the password. The workstation then requests the user's private key from a directory service of the remote server. The user's private key has previously been encrypted under the same secret encryption key and stored as a "credential" in the directory. A credential is a table entry comprising the user's name and the user's private RSA key; in other words, the credential is a representation of the user in the computer. The remote server returns the encrypted private key to the workstation, which uses the secret key to decrypt and obtain the private key.
In this password-based authentication system, the encrypted private key is transmitted over the network from the directory server to the workstation. Since knowledge of the password is not needed to initiate the request, an impostor can easily request a copy of the encrypted message. Equipped with a copy of the encrypted message, the impostor can attempt to decrypt the message by guessing various passwords and hashing them with the known hash-code algorithm to form the secret key. In other words, the impostor need only request the encrypted message once and, thereafter, it can continuously attempt to decipher the message on its own computer without the risk of being audited or detected. The impostor knows it has successfully derived the secret key and decrypted the message if the decrypted result yields an intelligible, valid private key. An impostor that can demonstrate possession of the private key may thus access system resources on behalf of the user.
A solution to this problem has been proposed using public key cryptography to enhance the security of a system that is primarily based on secret key authentication. This system employs a method to ensure that the contents of messages exchanged over the network are unintelligible to an impostor, even if the impostor has correctly decrypted a captured message. According to the method, the workstation generates a random bit string to which is concatenated a hash-coded version of the user's password. This quantity is encrypted under the authentication server's public key and forwarded, together with the username, as a message to the authentication server. The authentication server decrypts the message with its private key and checks that the workstation supplied the correct hash total for the user's password. If so, the server creates a ticket for the user and performs a boolean (exclusive-OR) function on the ticket and the random bit string. The result of this latter operation is encrypted under the user's password hash value and returned as a message to the workstation. Since the impostor does not know the random bit string, it cannot distinguish between successful and unsuccessful decryptions of the message. This is because there is no information in a successfully decrypted message that would provide the impostor with information that the decryption was successful.
It is apparent from the description above that the authentication server of the secret key system must have knowledge of the user's password. If the authentication server is compromised, it could use its knowledge of the password to impersonate the user. It is a significant advantage of a public key cryptography system that only the user has access to the user's private key. Yet, the lack of a trusted, on-line agent to oversee the login process makes the public key distributed system particularly vulnerable to a dictionary attack. The present invention is directed to the password guessing problem in a public key environment and provides the same degree of security against the dictionary attack as the above-described secret key system without revealing the private key to any other party.